package com.ljy.my_study.leetcode.组合总和II;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TestMain {

//    给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
//    candidates 中的每个数字在每个组合中只能使用一次。
//
//    注意：解集不能包含重复的组合。 
//
//             
//
//    示例 1:
//
//    输入: candidates = [10,1,2,7,6,1,5], target = 8,
//    输出:
//            [
//            [1,1,6],
//            [1,2,5],
//            [1,7],
//            [2,6]
//            ]
//    示例 2:
//
//    输入: candidates = [2,5,2,1,2], target = 5,
//    输出:
//            [
//            [1,2,2],
//            [5]
//            ]
//             
//
//    提示:
//
//            1 <= candidates.length <= 100
//            1 <= candidates[i] <= 50
//            1 <= target <= 30
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/combination-sum-ii
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {

    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(candidates);
        int len=candidates.length;
        if(len==0||candidates[0]>target){
            return result;
        }
        for(int i=0;i<len;i++){
            if(i>0&&candidates[i]==candidates[i-1]){
                continue;
            }
            List<Integer> list=new ArrayList<>();
            list.add(candidates[i]);
            if(candidates[i]==target){
                result.add(list);
                break;
            }
            dfs(candidates,i+1,list,result,target-candidates[i]);
        }
        return result;
    }

    private void dfs(int[] candidates,int index,List<Integer> list,List<List<Integer>> result,int target){
        int len=candidates.length;
        for(int i=index;i<len;i++){
            if(i>index&&candidates[i]==candidates[i-1]){
                continue;
            }
            int num=candidates[i];
            if(num<=target){
                list.add(candidates[i]);
                if(num==target){
                    result.add(new ArrayList<>(list));
                    list.remove(list.size()-1);
                    return;
                }
                dfs(candidates,i+1,list,result,target-num);
                list.remove(list.size()-1);
            }else {
                return;
            }
        }
    }
}
